package com.itheima.datastructure.linkedlist;

/**
 * @author tantao
 * @version 1.0
 * @description: TODO
 * @date 2025/8/26 10:26
 */

/**
 * 反转链表
 */
@SuppressWarnings("all")
public class E01Leetcode206Reverse {


    /**
     * 反转链表1 : 构造新节点的方式
     *
     * @param head
     * @return
     */
    public ListNode reverseList1(ListNode head) {
        ListNode newHead = null;
        ListNode temp = head;
        while (temp != null) {
            ListNode newNode = new ListNode(temp.val, newHead);
            newHead = newNode;
            temp = temp.next;
        }
        return newHead;
    }


    /**
     * 反转链表2 : 从一个链表中移除头节点，添加到另一个链表头部
     *
     * @param head 链表的头节点
     * @return 反转后的链表头节点
     */
    public ListNode reverseList2(ListNode head) {
        List oldList = new List(head);
        List newList = new List(null);

        while (true) {
            ListNode first = oldList.removeFirst();
            if (first == null) {
                break;
            }
            newList.addFirst(first);
        }
        return newList.head;
    }


    /**
     * 反转链表3： 递归
     *
     * @param p
     * @return
     */
    public ListNode reverseList3(ListNode cur) {
        if (cur == null || cur.next == null) {
            return cur; // 最后节点
        }

        ListNode last = reverseList3(cur.next);
        //----- '归'的过程图示1：
        //例：cur=4[4->5]                 --> 此处让 5->4  4->null 得到了 5->4->null
        //例：cur=3[3->5->4]              --> 此处让 4->3  3->null 得到了 5->4->3->null
        //例：cur=2[2->3->5->4]           --> 此处让 4->3->2  3->null 得到了 5->4->3->2->null
        //例：cur=1[1->2->3->5->4]        --> 此处让 4->3->2->1  2->null 得到了 5->4->3->2->1->null

        //----- '归'的过程图示2：
        // cur=4时,5->4, 4->null :   | 4 | 5 | null  -> | 5 | 4 | null
        // cur=3时,4->3 ,3->null :   | 3 | 5 | 4 | null -> | 5 | 4 | 3 | null
        // cur=2时,3->2, 2->null :   | 2 | 3 | 5 | 4 | null -> | 5 | 4 | 3 | 2 | null
        // cur=1时,2->1, 1->null :   | 1 | 2 | 3 | 5 | 4 | null -> | 5 | 4 | 3 | 2 | 1 | null

        cur.next.next = cur;

        cur.next = null;
        //返回最后的节点
        return last;
    }

    /**
     * 不断的从旧链表取出第二个节点，然后将取出的节点插入到新链表的头部 （用一个链表模拟了两个链表）
     *
     * @param o1 旧链表的头节点
     * @return 新链表的头节点
     * @return
     */

    public ListNode reverseList4(ListNode o1) {
        if (o1 == null || o1.next == null) {
            return o1;
        }
        //o1-旧链表的头部
        //o2-旧链表的第二个节点
        //n1-新链表的头部指针
        ListNode o2 = o1.next;
        ListNode n1 = o1;
        while (o2 != null) {
            // 取出o2
            o1.next = o2.next;
            // 插入到n1前面
            o2.next = n1;
            //更新n1
            n1 = o2;
            //移动o2,本来应该是o2 = o2.next,但是此时o2.next已经修改了
            o2 = o1.next;
        }
        return n1;

    }

    /**
     * 方法2的面向过程版本：从旧链表依次取出节点，添加到新链表头部
     *
     * @param o1
     * @return
     */
    public ListNode reverseList5(ListNode o1) {
        //新链表头节点
        ListNode n1 = null;
        //旧链表当前节点
        ListNode cur = o1;
        while (null != cur) {
            //记录下一个节点
            ListNode cNextt = cur.next;
            //添加到新链表头部
            cur.next = n1;
            //更新n1
            n1 = cur;
            //移动
            cur = cNextt;
        }
        return n1;
    }


    public static void main(String[] args) {
        ListNode o5 = new ListNode(5, null);
        ListNode o4 = new ListNode(4, o5);
        ListNode o3 = new ListNode(3, o4);
        ListNode o2 = new ListNode(2, o3);
        ListNode o1 = new ListNode(1, o2);
        System.out.println(o1);
        ListNode n1 = new E01Leetcode206Reverse().reverseList3(o1);
        System.out.println(n1);
    }

    static class ListNode {

        int val;
        ListNode next;

        public ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }


        @Override
        public String toString() {
            StringBuilder sb = new StringBuilder(64);
            sb.append("[");
            ListNode p = this;
            while (p != null) {
                sb.append(p.val);
                if (p.next != null) {
                    sb.append(",");
                }
                p = p.next;
            }
            sb.append("]");
            return sb.toString();
        }

    }

    static class List {
        //头节点
        ListNode head;


        public List(ListNode head) {
            this.head = head;
        }

        public void addFirst(ListNode first) {
            first.next = head;
            head = first;
        }

        public ListNode removeFirst() {
            ListNode first = head;
            if (null != first) {
                head = first.next;
            }
            return first;
        }


    }
}


